https://vazgriz.com/119/procedurally-generated-dungeons/
[Skip to content](#content "Skip to content"){.screen-reader-text .skip-link}
[VAZGRIZ](https://vazgriz.com/){rel="home"}
Menu
September 20, 2021November 18, 2019
by
vazgriz
I've been playing some roguelikes recently, so I wanted to try writing my own procedural dungeon generator. There are a lot of different ways to approach this problem, but I eventually decided to base mine off of TinyKeep's algorithm, [described here](https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/). I extended the algorithm to work in 3D, to create dungeons with multiple floors.
The code for this example is available in [this Github repo](https://github.com/vazgriz/DungeonGenerator). I'm using Unity3D for this demonstration, but these concepts are, of course, usable in any game engine.
{.wp-image-135 fetchpriority="high" decoding="async" width="624" height="632" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon13.png 624w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon13-296x300.png 296w" sizes="(max-width: 624px) 100vw, 624px"}
First, I had to write the algorithm to work in two dimensions. It works mostly the same as the TinyKeep algorithm, but has been simplified in some ways (especially room generation) and is more complex in others.
The scene for this example is Dungeon2D. The code for this is in the Scripts2D folder.
The world is divided into a rectangular grid. I assume that 1 unit is wide enough to represent a hallway. In a full game, 1 unit may correspond to 5 meters, for example. I chose a size of 30×30.
1\. Place rooms arbitrarily such that they don't overlap with each other. It doesn't matter that much how they are arranged, so for this example, I've just placed and sized them randomly. I've also added a 1 unit wide buffer on each side (to ensure that rooms aren't touching), but this is not required for the algorithm to work.
{.wp-image-121 decoding="async" width="732" height="597" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon1.png 732w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon1-300x245.png 300w" sizes="(max-width: 732px) 100vw, 732px"}
2\. Create a Delaunay triangulation graph of the rooms. I used the Bowyer-Watson algorithm. There are many implementations for this algorithm in many languages. I selected one that was easy to translate into C#.
{.wp-image-122 decoding="async" width="678" height="591" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon2.png 678w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon2-300x262.png 300w" sizes="(max-width: 678px) 100vw, 678px"}
3\. Create a minimum spanning tree (MST) from the triangulation. Here, I used Prim's algorithm. The MST guarantees that every room will be reachable. However, since it is a tree, it contains no cycles. There is only a single path from one room to any other room.
{.wp-image-123 loading="lazy" decoding="async" width="688" height="588" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon3.png 688w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon3-300x256.png 300w" sizes="(max-width: 688px) 100vw, 688px"}
4\. Create a list of hallways, starting with every edge in the tree from Step 3. The tree contains every room, so it guarantees that a path to every room exists. Randomly add edges from the triangulation graph to the list. This will add some cycles to hallways. Here, I used a 12.5% chance for each edge to be added.
{.wp-image-124 loading="lazy" decoding="async" width="653" height="590" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon4.png 653w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon4-300x271.png 300w" sizes="(max-width: 653px) 100vw, 653px"}
5\. For every hallway in the list, use the A\* algorithm to find paths from the start of a hallway to the end. After one path is found, it modifies the state of the world, so that future hallways can path around existing ones.
The cost function I used makes it cheaper to go through a hallway that another iteration carved, than to make a new hallway. This encourages the pathfinder to combine hallways that pass through the same area. Going through a room is possible, but expensive. So in most cases, the pathfinder will prefer to go around rooms.
{.wp-image-125 loading="lazy" decoding="async" width="813" height="551"}
Here's some examples of this algorithm using actual art assets (the assets and the code to place them is not in the repo):
{.wp-image-135 fetchpriority="high" decoding="async" width="624" height="632" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon13.png 624w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon13-296x300.png 296w" sizes="(max-width: 624px) 100vw, 624px"}
{.wp-image-136 loading="lazy" decoding="async" width="1024" height="576" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon14-1024x576.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon14-300x169.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon14-768x432.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon14-1536x864.png 1536w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon14.png 1920w" sizes="(max-width: 1024px) 100vw, 1024px"}
::: iframe
Unable to execute JavaScript.
:::
Now that I had a working dungeon generator in 2D, I started working to move it to 3D. All of the algorithms used have 3D versions, so it should be easy, right?
The grid is now 30x5x30.
1\. The first change was to generate rooms in 3D. This change was trivial.
{.wp-image-127 loading="lazy" decoding="async" width="867" height="612" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon6.png 867w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon6-300x212.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon6-768x542.png 768w" sizes="(max-width: 867px) 100vw, 867px"}
2\. Next, find the 3D Delaunay triangulation of the rooms, or rather the Delaunay tetrahedralization. Searching for either " 3D Delaunay triangulation" or " Delaunay tetrahedralization" returned a lot of research papers but no actual source code that I could find.
The closest was CGAL's implementation of 3D triangulation, but there were two problems with it. One was that this module was only available under the GPL ????. The other was that the code was so heavily templated and inscrutable, that I didn't actually find where they implemented the algorithm.
In the end, I had to learn how the Bowyer-Watson algorithm actually worked so I could change it myself. I still don't really understand why circumcircles are so important, but I was at least able to write it using circumspheres instead, using [this page](http://mathworld.wolfram.com/Circumsphere.html) from Wolfram MathWorld. Since it's mostly 4×4 matrix operations I just used Unity3D's `Matrix4x4` type to do the heavy lifting.
This new version is in `Scripts3D/Delaunay3D.cs`, in case anyone else was looking for an MIT licensed, easy to understand version.
{.wp-image-128 loading="lazy" decoding="async" width="800" height="600"}
It's hard to see, but instead of producing triangles with 3 vertices, the algorithm now produces tetrahedra with 4 vertices. At least one of those vertices will be on a different floor, otherwise the tetrahedron would be degenerate. This gives the pathfinding step plenty of opportunities to move between floors.
3 and 4. The edges from Step 2 can be fed into Prim's algorithm with only trivial changes.
{.wp-image-130 loading="lazy" decoding="async" width="800" height="587" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon8.png 800w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon8-300x220.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon8-768x564.png 768w" sizes="(max-width: 800px) 100vw, 800px"}
{.wp-image-131 loading="lazy" decoding="async" width="808" height="575" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon9.png 808w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon9-300x213.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon9-768x547.png 768w" sizes="(max-width: 808px) 100vw, 808px"}
5\. The 3D A\* is where it gets complicated. The 2D version is the dead simple, standard implementation of A\*. To make it 3D, I had to add the ability for the pathfinder to move up and down and connect rooms on different floors. I chose to connect floors using staircases rather than, say, a ladder.
This is where the problem lies. A staircase is more complex than simply moving straight up. The staircase must move horizontally in order to move vertically. That is, there is a *rise* and a *run*. Consider the image below. The current cell is the solid blue square. The possible neighbors are the hollow squares. The pathfinder cannot move to the cell directly above the current cell. Instead, it has to move horizontally and vertically at the same time.
{.wp-image-132 loading="lazy" decoding="async" width="185" height="125"}
I had to choose the shape of the staircase in order to build a pathfinder for it. A rise to run ratio of 1:1 would be too steep, so I settled for a ratio of 1:2. It would move horizontally by two units for every vertical unit. Additionally, there must be headroom for characters to stand above the staircase itself, so the two cells directly above the staircase must be open as well. In total, there are four cells occupied by one staircase:
{.wp-image-133 loading="lazy" decoding="async" width="130" height="125"}
There must also be a hallway at the top and bottom of the stairs. The pathfinder cannot move into the staircase from the sides or the from the opposite direction. It would be impractical and look strange for a staircase to cut through a hallway like the images below.
{.wp-image-147 loading="lazy" decoding="async" width="739" height="568" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon25.png 739w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon25-300x231.png 300w" sizes="(max-width: 739px) 100vw, 739px"}
{.wp-image-148 loading="lazy" decoding="async" width="704" height="605" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon26.png 704w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon26-300x258.png 300w" sizes="(max-width: 704px) 100vw, 704px"}
So in the end, the staircase shape must look like the image below. The pathfinder must guarantee that the hallways at the two blue squares exist.
{.wp-image-134 loading="lazy" decoding="async" width="257" height="125"}
The pathfinder must move from the starting location to the end location in one step. This means it must move 3 units horizontally and 1 unit up or down. The A\* algorithm is designed to move from one node to an adjacent node every step. To make staircases, I would need to "jump over" the four cells of the staircase.
The hard part is that I need to somehow make the pathfinder work around staircases that it creates. I can't add them to the *closed set* of A\*, since that would prevent a different path from going through those cells from a different direction. But I can't leave them out, because then the pathfinder would be able to move through a staircase it just created, creating those unwanted situations pictured above.
The solution was for each node to keep track of all previous nodes in it's path. Then when a neighbor node is being evaluated, it will be rejected if it falls on the path of the current node. The hallway at the end of the staircase would contain all of the cells occupied by the staircase, the node at the start of the staircase, and all nodes in the path before that, all the way to the start. The pathfinder could create another path that passes through the staircase, since the second path wouldn't know about the staircase.
The above behavior is only for multiple potential paths within one call to the pathfinding function. There are still multiple pathfinding calls to generate all the hallways. Later iterations will just work around existing staircases like before.
The algorithm isn't exactly A\* at this point. There are too many special cases just to handle staircases. Having to check the entire previous path on each step is expensive. The naive implementation would be to follow the nodes all the way to the start, reading them like a linked list. That would make checking the path O(N), for every neighbor node.
The implementation I went with was to maintain a hashtable in each node that is keyed with the previous nodes. That makes checking the path O(1), but the hashtable must be copied when a node is added to the path, which is O(N). I chose this method because I figured that the algorithm would be reading paths more often than it modified them.
Either way, the overall complexity should be about O(N\^2), though I don't really know how to analyze it properly. This modification is the main bottleneck of the dungeon generation algorithm.
After all these changes are made, this is the result:
{.wp-image-144 loading="lazy" decoding="async" width="800" height="600"}
{.wp-image-145 loading="lazy" decoding="async" width="677" height="547" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon23.png 677w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon23-300x242.png 300w" sizes="(max-width: 677px) 100vw, 677px"}
{.wp-image-146 loading="lazy" decoding="async" width="1025" height="607" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon24.png 1025w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon24-300x178.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon24-768x455.png 768w" sizes="(max-width: 1025px) 100vw, 1025px"}
Here's a 3D dungeon with actual art assets:
{.wp-image-137 loading="lazy" decoding="async" width="1024" height="524" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon15-1024x524.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon15-300x153.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon15-768x393.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon15.png 1181w" sizes="(max-width: 1024px) 100vw, 1024px"}
::: iframe
Unable to execute JavaScript.
:::
The dungeon generation algorithm can create some interesting emergent behavior.
{.wp-image-138 loading="lazy" decoding="async" width="1024" height="538" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon16-1024x538.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon16-300x158.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon16-768x403.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon16.png 1089w" sizes="(max-width: 1024px) 100vw, 1024px"}
{.wp-image-143 loading="lazy" decoding="async" width="1024" height="578" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon21-1024x578.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon21-300x169.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon21-768x433.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon21.png 1092w" sizes="(max-width: 1024px) 100vw, 1024px"}
{.wp-image-139 loading="lazy" decoding="async" width="1024" height="570" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon17-1024x570.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon17-300x167.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon17-768x427.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon17.png 1077w" sizes="(max-width: 1024px) 100vw, 1024px"}
{.wp-image-141 loading="lazy" decoding="async" width="1024" height="582" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon19-1024x582.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon19-300x171.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon19-768x437.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon19.png 1073w" sizes="(max-width: 1024px) 100vw, 1024px"}
{.wp-image-142 loading="lazy" decoding="async" width="1024" height="570" srcset="https://vazgriz.com/wp-content/uploads/2019/11/dungeon20-1024x570.png 1024w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon20-300x167.png 300w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon20-768x428.png 768w, https://vazgriz.com/wp-content/uploads/2019/11/dungeon20.png 1097w" sizes="(max-width: 1024px) 100vw, 1024px"}
The hardest part of this project was making the algorithms needed for the 3D version. I couldn't find any implementations of 3D Delaunay triangulation, so I had to make one myself. The pathfinder's requirements were very specific to my project, so I had to make it myself.
It was worth it. The dungeons created by this algorithm are interesting and might just make a basis for a good game.
Categories [Procedural Content Generation](https://vazgriz.com/category/programming/pcg/){rel="category tag"}
Tags [C#](https://vazgriz.com/tag/csharp/){rel="tag"}, [Unity3D](https://vazgriz.com/tag/unity3d/){rel="tag"}
[Optimizing a Vulkan Program Part 3: Further Optimizations](https://vazgriz.com/84/optimizing-a-vulkan-program-part-3-further-optimizations/){rel="prev"}
[Reflex Sight Shader in Unity3D](https://vazgriz.com/158/reflex-sight-shader-in-unity3d/){rel="next"}
1. [Pingback: [D&D Dungeon Generation -- HvA GPE Gamelab](https://summit-2223-sem1.game-lab.nl/?p=49){.url rel="ugc external nofollow"}]{#comment-1}
Comments are closed.
Search for:
[Youtube channel](https://www.youtube.com/channel/UCZKWZx19viaufZY_UJZqG2w)
- [Translating a Fortran F-16 Simulator to Unity3D](https://vazgriz.com/762/f-16-flight-sim-in-unity-3d/)
- [Announcing Double Flash Studios](https://vazgriz.com/723/announcing-double-flash-studios/)
- [PID Controllers in Unity3D](https://vazgriz.com/621/pid-controllers/)
- [Drawing Mushrooms with Vulkan](https://vazgriz.com/565/drawing-mushrooms-with-vulkan/)
- [Creating a Flight Simulator in Unity3D Part 3: Weapons and AI](https://vazgriz.com/503/creating-a-flight-simulator-in-unity3d-part-3/)
- [June 2025](https://vazgriz.com/date/2025/06/)
- [February 2023](https://vazgriz.com/date/2023/02/)
- [December 2021](https://vazgriz.com/date/2021/12/)
- [June 2021](https://vazgriz.com/date/2021/06/)
- [April 2021](https://vazgriz.com/date/2021/04/)
- [February 2021](https://vazgriz.com/date/2021/02/)
- [January 2021](https://vazgriz.com/date/2021/01/)
- [December 2019](https://vazgriz.com/date/2019/12/)
- [November 2019](https://vazgriz.com/date/2019/11/)
- [May 2019](https://vazgriz.com/date/2019/05/)
- [Double Flash Studios](https://vazgriz.com/category/double-flash-studios/)
- [Flight Sim](https://vazgriz.com/category/programming/flight-sim/)
- [Procedural Content Generation](https://vazgriz.com/category/programming/pcg/)
- [Programming](https://vazgriz.com/category/programming/)
- [Shaders](https://vazgriz.com/category/programming/shaders/)
- [VkColors](https://vazgriz.com/category/programming/vkcolors/)
- [Log in](https://vazgriz.com/wp-login.php)
- [Entries feed](https://vazgriz.com/feed/)
- [Comments feed](https://vazgriz.com/comments/feed/)
- [WordPress.org](https://wordpress.org/)
© 2026 VAZGRIZ • Built with [GeneratePress](https://generatepress.com){itemprop="url"}
{{backlinks}}